This chapter discusses in detail the stack and queue objects included in the Containers Library. It describes how to use these objects and the different types of stacks and queues available.
In this chapter you will learn:
- What are stacks?
- The general characteristics of stacks
- What are queues?
- The general characteristics of queues
What are stacks?
A stack is formally defined as a list in which all insertions and deletions are made at one end of the list, usually referred to as the top of the list. When an element is inserted in a stack, it is said it was pushed into the list. When an element is deleted from a stack, it is said it was popped from the list.
Stacks are known as LIFO or last-in-first-out lists, which means that the first item added to the list will always be the last one to be removed. This is useful for such things as eliminating recursive procedures in tree structures or writing compilers, for example.
Using the stacks
All stacks inherit their functionality from other more complex containers like the arrays, the collections and the linked lists. How you use a stack depend on the container on which it is based. For example, the TArrayStack uses a resizable dynamic array to store items in the list, while TLinkedStack uses a TList container to build a linked list of items. All stacks implement the following additional methods used to access the data in the stack:
- Push : inserts an item at the top of the stack
- Pop : removes an item from the top of the stack
- Top : returns the item at the top of the stack
- Bottom : returns the item at the bottom of the stack
Since data items are stored in memory at all times, the use of DoneItem is not required. However, if you intend to write data-structure independent applications, you must still always use it after retrieving an item from the container.
What are queues?
Queues are lists in which all insertions to the list are made at one end of the list, and deletions are made at the other end. The end at which insertions are made is usually referred to as the front and the end at which deletions are made is usually referred to as the rear.
Queues are also known as FIFO or first-in-first-out lists, which means that the first item added to the list will always be the first to be removed. These structures are useful for such things as background printer jobs.
Only two queues are included in the Containers Library, both of which are linked lists. The double-ended queue lets you access items from either end of the list.
Using the queues
Queues are TList descendants that work in the same way as linked list containers. However, additional methods are used to provide the functionality of the queue:
- EnQueue : inserts an item at the rear (end) of the queue.
- Remove : removes an item from the front of the queue.
- Front : returns the first item in the queue (the first
item that will be removed).
- Rear : returns the last item in the queue (the last
item to that will be removed).
The double ended queue also provides the following methods:
- RemoveFirst : removes the first item in the queue
- RemoveLast : removes the last item in the queue
Since data items are stored in memory at all times, the use of DoneItem is not required. However, if you intend to write data-structure independent applications, you must still always use it after retrieving an item from the container.
